package org.ala.everyday;

import java.util.Map;
import java.util.Set;

/**
 * 汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。
 *
 * 沿途有加油站，用数组 stations 表示。其中 stations[i] = [positioni, fueli] 表示第 i 个加油站位于出发位置东面 positioni 英里处，并且有 fueli 升汽油。
 *
 * 假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。
 *
 * 为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。
 *
 * 注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。
 *
 *
 *
 * 示例 1：
 *
 * 输入：target = 1, startFuel = 1, stations = []
 * 输出：0
 * 解释：可以在不加油的情况下到达目的地。
 * 示例 2：
 *
 * 输入：target = 100, startFuel = 1, stations = [[10,100]]
 * 输出：-1
 * 解释：无法抵达目的地，甚至无法到达第一个加油站。
 * 示例 3：
 *
 * 输入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
 * 输出：2
 * 解释：
 * 出发时有 10 升燃料。
 * 开车来到距起点 10 英里处的加油站，消耗 10 升燃料。将汽油从 0 升加到 60 升。
 * 然后，从 10 英里处的加油站开到 60 英里处的加油站（消耗 50 升燃料），
 * 并将汽油从 10 升加到 50 升。然后开车抵达目的地。
 * 沿途在两个加油站停靠，所以返回 2 。
 *
 *
 * 提示：
 *
 * 1 <= target, startFuel <= 109
 * 0 <= stations.length <= 500
 * 1 <= positioni < positioni+1 < target
 * 1 <= fueli < 109
 *
 * @author ala
 * @date 2024-10-07 01:01
 */
public class Q871 {

    public static void main(String[] args) {
        Q871 q = new Q871();

//        int target = 1, startFuel = 1;
//        int[][] stations = {};

        int target = 100, startFuel = 1;
        int[][] stations = {{10, 100}};

//        int target = 100, startFuel = 10;
//        int[][] stations = {{10,60},{20,30},{30,30},{60,40}};

        System.out.println(q.minRefuelStops(target, startFuel, stations));
    }

    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        return V1(target, startFuel, stations);
    }
    static int INF = Integer.MIN_VALUE >> 1;
    /**
     *  1）dp[i][j]表示：到达第i个加油站时，总共加了j次油（dp[1]对应stations[0]，含第i个加油站）剩余油量
     *      i ∈ [0, N], i ∈ [0, N-1]
     *      加上target油量为0的虚拟加油站
     *  2）dp[0][0] = startFuel，初始化最小加油次数：mn = 0
     *  3）定义：d = stations[i][0] - stations[i - 1][0]，表示两个加油站之间的里程数
     *      如果：dp[i][i] < d，说明即便吃满，也无法到达下个加油站，直接-1
     *      j 从 mn 到 i：
     *          如果dp[i - 1][j] < d：说明加j次油无法到达i，mn = j+1
     *          dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + stations[i - 1][1]) - d
     *  4）最后mn就是答案
     */
    protected int V1(int target, int startFuel, int[][] stations) {
        int N = stations.length;
        if (N == 0) {return startFuel >= target ? 0 : -1;}
        //  第0个加油站是起点，里程数为0。第 N + 1 个加油站是终点，油量为0
        //  总共可以加 0, 1, 2, ... , N, N+1 次油（最后一次加油量为0）
        int[][] dp = new int[N + 2][N + 2];
        dp[0][0] = startFuel;
        int prev = 0;
        for (int i = 1 ; i <= N + 1; i++) {
            //  第i个加油站的里程数和油量
            int crt = i == 0 ? 0 : (i == N + 1 ? target : stations[i - 1][0]);
            int d = crt - prev;
            prev = crt;
            int fuel = i == 0 ? startFuel : (i == N + 1 ? 0 : stations[i - 1][1]);
            //  检测从 i-1 出发，能否到达 i（在第 i-1 个加油站，最多加油 i-1 次）
            boolean succ = false;
            for (int j = 0 ; j < i ; j++) {
                //  如果第j次加油的剩余油量不能到达，直接给负
                if (dp[i - 1][j] < 0 || dp[i - 1][j] - d < 0) {
                    dp[i][j] = INF;
                }
                //  如果可以到达，可以选择加油或者不加油
                else {
                    succ = true;
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j] - d);
                    dp[i][j + 1] = Math.max(dp[i][j], dp[i - 1][j] - d + fuel);
                }
            }
            //  如果所有加油次数均不能到达，直接-1
            if (!succ) {
                return -1;
            }
        }
        //  判断在第 N+1 个加油站（终点），剩余油量>=0的最小加油次数就是答案
        for (int j = 0 ; j <= N ; j++) {
            if (dp[N + 1][j] >= 0) {
                return j;
            }
        }
        return -1;
    }
}
